public class 二叉树的完全性检验 {
    //https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/
    //判断是否为完全二叉树
    //1. 左子树不存在右子树存在
    //2. 已经存在一个节点不存在右子树, 后面的节点的子树必须都为空
    //手写队列
    public static int MAXH = 101;
    public static boolean flag;
    public static TreeNode[] queue = new TreeNode[MAXH];
    public static int l;
    public static int r;

    //
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        //flag是拿来判断是否存在一个节点的左右节点为空, 如果为空就相当于启动了开关一样
        flag = false;
        return dfs(root);
    }
    public boolean dfs(TreeNode root){
        l = r = 0;
        queue[r++] = root;
        while(l < r){
            TreeNode t = queue[l++];
            //第一个判断点
            if(t.left == null && t.right != null){
                return false;
            }
            //第二个判断点
            if(flag && (t.left != null || t.right != null)){
                return false;
            }
            if(t.left != null){
                queue[r++] = t.left;
            }
            if(t.right != null){
                queue[r++] = t.right;
            }
            //开关的设置
            if(t.left == null || t.right == null){
                flag = true;
            }
        }
        return true;
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        // 无参构造函数
        TreeNode() {}

        // 只带一个值的构造函数
        TreeNode(int val) {
            this.val = val;
        }

        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
